package com.sheng.leetcode.year2022.month07.day27;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/07/27
 *
 * 592. 分数加减运算
 *
 * 给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。 
 * 这个结果应该是不可约分的分数，即最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。
 *
 * 示例 1:
 * 输入: expression = "-1/2+1/2"
 * 输出: "0/1"
 *
 * 示例 2:
 * 输入: expression = "-1/2+1/2+1/3"
 * 输出: "1/3"
 *
 * 示例 3:
 * 输入: expression = "1/3-1/2"
 * 输出: "-1/6"
 *
 * 提示:
 *
 * 输入和输出字符串只包含 '0' 到 '9' 的数字，以及 '/', '+' 和 '-'。 
 * 输入和输出分数格式均为 ±分子/分母。如果输入的第一个分数或者输出的分数是正数，则 '+' 会被省略掉。
 * 输入只包含合法的最简分数，每个分数的分子与分母的范围是  [1,10]。 如果分母是1，意味着这个分数实际上是一个整数。
 * 输入的分数个数范围是 [1,10]。
 * 最终结果的分子与分母保证是 32 位整数范围内的有效整数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/fraction-addition-and-subtraction
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0592 {

    @Test
    public void test01() {
//        String expression = "-1/2+1/2";
//        String expression = "-1/2+1/2+1/3";
        String expression = "1/3-1/2";
        System.out.println(new Solution().fractionAddition(expression));
    }

}
class Solution {
    public String fractionAddition(String expression) {
        //1.将字符串拆分成多个
        List<String> list = new ArrayList<String>();
        int index = 0;
        for (int i = 0; i < expression.length(); i++) {
            if (i == expression.length() - 1) {
                list.add(expression.substring(index, i + 1));
            }
            if (i != 0 && (expression.charAt(i) == '+' || expression.charAt(i) == '-')) {
                list.add(expression.substring(index, i));
                index = i;
            }
        }
        String ans = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            //2.一个方法，对两个字符串进行相加
            ans = add(ans, list.get(i));
        }
        //3.对字符串进行简化
        //分别获取字符串的分子和分母
        String[] split = ans.split("/");
        //分子
        int molecule = Integer.parseInt(split[0]);
        //分母
        int denominator = Integer.parseInt(split[1]);
        //判断分子和分母之间是否存在大于1的公因数，存在则化简
        while (getCommonFactor(Math.abs(molecule), Math.abs(denominator)) > 1) {
            int commonFactor = getCommonFactor(Math.abs(molecule), Math.abs(denominator));
            molecule = molecule / commonFactor;
            denominator = denominator / commonFactor;
        }
        return molecule + "/" + denominator;
    }

    public String add(String str1, String str2) {
        String[] split1 = str1.split("/");
        //分子
        int molecule1 = Integer.parseInt(split1[0]);
        //分母
        int denominator1 = Integer.parseInt(split1[1]);
        String[] split2 = str2.split("/");
        int molecule2 = Integer.parseInt(split2[0]);
        int denominator2 = Integer.parseInt(split2[1]);
        if (molecule1 == 0) {
            return str2;
        } else if (molecule2 == 0) {
            return str1;
        }
        //求两个分母之间的最小公倍数
        int commonMultiple = getCommonMultiple(denominator1, denominator2);
        int sum = molecule1 * commonMultiple / denominator1 + molecule2 * commonMultiple / denominator2;
        if (sum == 0) {
            return "0/1";
        }
        return sum + "/" + commonMultiple;
    }

    //求最大公因数
    public int getCommonFactor(int num1, int num2) {
        if (num2 == 0) {
            return num1;
        } else {
            return getCommonFactor(num2 , num1 % num2);
        }
    }

    //求最小公倍数
    public int getCommonMultiple(int num1, int num2) {
        return num1 * num2 / getCommonFactor(num1, num2);
    }
}
